package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/14.<br><br>
 *
 * 比特位计数
 */
public class Topic338 {

    public static void main(String[] args) {
        Topic338 instance = new Topic338();

        Util.printArray(instance.countBits(2));
        Util.printArray(instance.countBits(5));
    }

    public int[] countBits(int n) {
        int[] result = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            int counter = 0;
            int temp = i;
            while (temp != 0) {
                counter += temp & 1;
                temp = temp >>> 1;
            }

            result[i] = counter;
        }

        return result;
    }

    public int[] countBits2(int n) {
        int[] result = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            int counter = 0;
            int temp = i;
            for(; temp != 0; counter++) {
                temp = temp & (temp - 1);
            }

            result[i] = counter;
        }

        return result;
    }
}
